求和 (sum) 的题解

题目背景

AC_Automation 作为一个可爱的妹子,她喜欢求和而不喜欢乘积。她现在有一个序列,想让你求一些东西。看在她那么可爱的份上,就帮帮她吧。

题目描述

为了让你解出题目,善良的她定义了两个函数: f(l,r)f(l, r)g(l,r)g(l, r) ,满足:

f(l,r)=i=lrAi=Al+Al+1+... +Arf(l, r) = \sum^{r}_{i = l} A_i = A_l + A_{l + 1} + ... \text{ +} A_r

g(l,r)=lijrf(i,j)g(l, r) = \sum_{l \le i \le j \le r} f(i, j)

(例如:g(1,3)=f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)g(1, 3) = f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3)

现在她给了你一个长度为 nn 的序列 AnA_n ,以及 TT 个询问,对于第 ii 个询问 li,ril_i, r_i ,请你求出对应的 g(li,ri)g(l_i, r_i)

由于她太菜了,看在她那么可爱的份上,就帮帮她吧。

输入格式

第一行两个整数 nnTT ,分别表示序列长度和询问的个数

第二行 nn 个正整数 AiA_i ,表示 AC_Automation 给你的一个序列。

接下来 TT 行,每行一个 lil_irir_i ,表示 TT 个询问。

输出格式

TT 行,表示每个 lil_irir_i 所对应的 g(li,ri)g(l_i, r_i)

样例输入

3 3
1 2 3
1 2
1 3
2 3

样例输出

6
20
10

提示说明

【数据范围与约定】

测试点序号 nn\le TT\le
151 \sim 5 100100 5050
6106 \sim 10 500500 100100
111511 \sim 15 10410^4 10310^3
162016 \sim 20 10610^6 10610^6

对于 100%100\% 的数据,1n1061 \le n\le 10^61T1061 \le T\le 10^61Ai321 \le A_i \le 32

题解

首先,很显然我们可以去算每个数的贡献,算得:

g(l,r)=i=lr(il+1)(ri+1)Aig(l, r) = \sum^{r}_{i = l} (i - l + 1) \cdot (r - i + 1) \cdot A_i

我们用 22 种方法来解这道题:

第一种,整体法 (by 2x6_81)

在开始这个方法之前,先定义一个东西叫做“在 lrl \sim r 之间的贡献三角形”。如下图所示:

AlA_l Al+1A_{l + 1} \cdots ArA_r
rl+1r - l + 1 rlr - l \cdots 11
rlr - l \cdots 11
\cdots 11
\cdots
11

l=5,r=8l = 5, r = 8 为例:

A5A_5 A6A_6 A7A_7 A8A_8
44 33 22 11
33 22 11
22 11
11

可以发现,将每一列的数乘起来再求和就是答案。例如上表,g(5,8)=(4)A5+(3+3)A6+(2+2+2)A7+(1+1+1+1)A8g(5, 8) = (4) \cdot A_5 + (3 + 3) \cdot A_6 + (2 + 2 + 2) \cdot A_7 + (1 + 1 + 1 + 1) \cdot A_8

n=7n = 7 为例,我们先求出 171 \sim 7 的贡献三角形:

A1A_1 A2A_2 A3A_3 A4A_4 A5A_5 A6A_6 A7A_7
77 66 55 44 33 22 11
66 55 44 33 22 11
55 44 33 22 11
44 33 22 11
33 22 11
22 11
11

假设我们要求出 l=3,r=5l = 3, r = 5 时的结果,也就是 353 \sim 5 的贡献三角形,就可以这么求:

第一步,求出 171 \sim 7 的贡献三角形中的前 55 列,如下图所示:

A1A_1 A2A_2 A3A_3 A4A_4 A5A_5
77 66 55 44 33
66 55 44 33
55 44 33
44 33
33

第二步,求出 171 \sim 7 的贡献三角形中的第 353 \sim 5 列,如下图所示:

A3A_3 A4A_4 A5A_5
55 44 33
55 44 33
55 44 33
44 33
33

可以发现,前两步所用的东西是可以通过预处理 (n+1i)iAi(n + 1 - i) \cdot i \cdot A_i 的前缀和得到。

第三步,三角形只保留 3333 列,如下图所示:

A3A_3 A4A_4 A5A_5
55 44 33
44 33
33

这里可以通过减去一个 i=352(8i)Ai\sum^{5}_{i = 3} 2 \cdot (8 - i) \cdot A_i 得到该结果,可以发现,这个东西可以通过预处理 AiA_i(ni)Ai(n - i) \cdot A_i 的前缀和得到。

最后一步,将每个数减掉 22 ,如下图所示:

A3A_3 A4A_4 A5A_5
33 22 11
22 11
11

这里可以通过减去一个 i=352(i2)Ai\sum^{5}_{i = 3} 2 \cdot (i - 2) \cdot A_i 得到该结果,可以发现,这个东西可以通过预处理 AiA_iiAii \cdot A_i 的前缀和得到。

综上,可以发现答案是:

i=lr(n+1i)iAi(l1)i=lr(n+1i)Ai(nr)i=lr(il+1)Ai\sum^{r}_{i = l} (n + 1 - i) \cdot i \cdot A_i - (l - 1) \cdot \sum^{r}_{i = l} (n + 1 - i) \cdot A_i - (n - r) \cdot \sum^{r}_{i = l} (i - l + 1) \cdot A_i

通过预处理 (n+1i)iAi(n + 1 - i) \cdot i \cdot A_iiAii \cdot A_i(ni)Ai(n - i) \cdot A_iAiA_i 的前缀和即可

将其暴力拆开,得到:

i=lr((n+1i)i(l1)(n+1i)(nr)(il+1))Ai\sum^{r}_{i = l} ((n + 1 - i) \cdot i - (l - 1) \cdot (n + 1 - i) - (n - r) \cdot (i - l + 1)) \cdot A_i

=i=lr(ni+ii2lnl+li+n+1ini+nln+rirl+r)Ai= \sum^{r}_{i = l} (n \cdot i + i - i^2 - l \cdot n - l + l \cdot i + n + 1 - i - n \cdot i + n \cdot l - n + r \cdot i - r \cdot l + r) \cdot A_i

=i=lr(i2l+li+1+rirl+r)Ai= \sum^{r}_{i = l} (- i^2 - l + l \cdot i + 1 + r \cdot i - r \cdot l + r) \cdot A_i

=i=lr(i2+li+rirll+r+1)Ai= \sum^{r}_{i = l} (- i^2 + l \cdot i + r \cdot i - r \cdot l - l + r + 1) \cdot A_i

=i=lr(i2+(l+r)i(r+1)(l1))Ai= \sum^{r}_{i = l} (- i^2 + (l + r) \cdot i - (r + 1) \cdot (l - 1)) \cdot A_i

预处理 i2Ai-i^2 \cdot A_iiAii \cdot A_iAiA_i 的前缀和即可

第二种,隔离法 (by registerGen)

这个方法非常简单,我们对于每个 AiA_i 的贡献进行分解,得到如下变换:

i=lr(il+1)(ri+1)Ai=i=lr(i2+(l+r)i+(r+1)(l+1))Ai\sum^{r}_{i = l} (i - l + 1) \cdot (r - i + 1) \cdot A_i = \sum^{r}_{i = l} (-i^2 + (l + r) \cdot i + (r + 1) \cdot (-l + 1)) \cdot A_i

预处理 i2Ai-i^2 \cdot A_iiAii \cdot A_iAiA_i 的前缀和即可